The present embodiments relate to particle-based fluid simulation. In smoothed particle hydrodynamics (SPH), computational fluid simulation is based on the Monte Carlo method. Internal forces are calculated between pairs of particles. For example, density is calculated as
            ρ      i      f        =                  m        f            ⁢                        ∑          j                ⁢                  W          ⁡                      (                                          r                ij                            ,                              h                f                                      )                                ,where i and j are neighbor particles, m is the mass, r is the radius, h is a smoothing radius limiting interaction to a range, and W is a kernel function. Pressure force is calculated as
      F    i    pressure    =            -              m        f              ⁢                  ∑        j            ⁢                                                  (                                                P                  i                  f                                +                                  P                  j                  f                                            )                        ⁢                          ∇                              W                ⁡                                  (                                                            r                      ij                                        ,                                          h                      f                                                        )                                                                          2            ⁢                                                  ⁢                          ρ              j              f                                      .            Viscosity force is calculated as
      F    i    viscosity    =            m      f        ⁢    μ    ⁢                  ∑        j            ⁢                                                  (                                                v                  j                  f                                -                                  v                  i                  f                                            )                        ⁢                                          ∇                2                            ⁢                              W                ⁡                                  (                                                            r                      ij                                        ,                                          h                      f                                                        )                                                                          ρ            j                          .            The forces are used to simulate advecting of the particles. Over multiple iterations, velocity is calculated as
                    v        i        f            ⁡              (                  t          +                      1            2                          )              =                            v          i          f                ⁡                  (                      t            -                          1              2                                )                    +              a        ⁢                                  ⁢        Δ        ⁢                                  ⁢        t              ,and position is calculated as
            L      i      f        ⁡          (      t      )        =                    L        i        f            ⁡              (                  t          -          1                )              +                            v          i          f                ⁡                  (                      t            +                          1              2                                )                    ⁢      Δ      ⁢                          ⁢              t        .            
Since only particles within the smoothing radius, h, interact with each other, it is possible to avoid O(n2) calculations with all particles in the simulation. The need to simulate fluids at interactive speeds has further led to GPU-based implementation. By dividing the simulation space into cells, each of diminution equal to the smoothing radius, h, it is possible to iterate over all of a particle's neighbors at an order of O(mn), where m is the average number of particles per cell. If particle i is located at cell(x, y, z), iε cell (x, y, z) then a neighboring particle j belongs to cell(x, y, z)∪jε cell(x±1, y±1, z±1). Even with this efficiency, simulating at interactive speeds may be difficult. The influence of particles outside the smoothing radius is not considered.